\section{Bezpečnosť niektorých hašovacích funkcíí}

S hašovacími funkciami sme sa zoznámili v zimnom semestri.
Pripomeňme, že je to zobrazenie $h: X \to Y$, kde $Y$ je konečná množina.
Pre jednoduchosť predpokladajme, že $Y = \{0,1\}^n$. 

Dobrá hašovacia funkcia by mala spĺňať nasledovné požiadavky 
(vychádzajú z toho, že by sa mala čo najviac priblížiť náhodnému orákulu). 
Okrem požiadaviek zo zimného semestra formulujeme niekoľko ďalších:
\begin{enumerate}
    \itemsep -1.2mm
    \item Odolnosť prvého vzoru: K danému $y$ je ťažké nájsť $x$ také, 
        že $h(x) = y$. Očakávaný čas hľadania $x$ je $\Theta(2^n)$.

    \item Odolnosť druhého vzoru: K danému $x$ je ťažké nájsť 
        $z \neq x$ také, že $h(x) = h(z)$. Očakávaný čas hľadania je opäť
        $\Theta(2^n)$.

    \item Odolnosť proti kolíziám: Je ťažké nájsť $x \neq x$ také, 
        že $h(x) = h(z)$. Očakávaný čas hľadania je $\Theta(2^{n/2})$ 
        (narodeninový útok).

    \vskip 0.5cm

    \item $k$-odolnosť prvého vzoru: K danému $y$ je ťažké nájsť navzájom rôzne 
        $x_1, x_2, \dots, x_k$ také, že $h(x_i) = y$. Očakávaný čas hľadania
        je $\Theta(k 2^n)$.

    \item $k$-odolnosť druhého vzoru: K danému $x$ je ťažké nájsť
        navzájom rôzne 
        $x_1, x_2, \dots, x_k$ také, že $h(x_i) = h(x)$ a $x_i \neq x$.
        Očakávaný čas hľadania je $\Theta(k 2^n)$.

    \item $k$-odolnosť proti kolíziám: Je ťažké nájsť navzájom rôzne 
        $x_1, x_2, \dots, x_k$ také, že $\forall i, j\colon h(x_i) = h(x_j)$. 
        Dá sa ukázať, že pokiaľ je $k$ zanedbateľné oproti $2^n$, tak očakávaný 
        čas hľadania $k$-kolízie je $\Theta(2^{n(k-1)/k})$.
        Pre väčšie $k$ je očakávaný čas väčší.
\end{enumerate}

\subsection {Iteratívne konštrukcie hašovacích funcíí a ich slabiny}

Ide o konštrukciu hašovacej funkcie, ktorá opakovaným aplikovaním
hašovacej funkcie pracujúcej na vstupe pevnej dĺžky vyrobí hašovaciu
funkciu pracujúcu na binárnom reťazci neobmedzenej dĺžky.
Rozdeľme text $M$ na bloky $m_1, m_2, \dots, m_l$ rovnakej dĺžky
(v poslednom bloku môžeme očakávať nejaký padding).
Položme $h_0 = IV$ a $h_i = f(h_{i-1}, m_i)$ pre $i \geq 1$, kde $f$ 
je kompresná funkcia, ktorej obor hodnôt je $\{0,1\}^n$.
Výstupom hašovacej funkcie je hodnota $h_l$.

Takúto konštrukciu 
používa väčšina v súčasnosti používaných hašovacích funkcií
(MD5, SHA-1, SHA-xxx, \dots).

\begin{figure}[h!]
    \centering
    \includegraphics[scale=1.0]{img/05/iter.1.mps}
    \caption{Iteratívna hašovacia funkcia}
    \label{fig:iter}
\end{figure}


\noindent
V roku 2004 Joux našiel nasledujúci útok (\cite{Joux04}):

\begin{enumerate}
    \itemsep -1.2mm
    \item Položme $h_0 = IV$.

    \item Nájdime $m_1 \neq m_1'$ také, že $f(h_0, m_1) = f(h_0, m_1') = h_1$, 
        toto vieme v čase $O(2^{n/2})$.

    \item Podobne nájdime dvojice $m_2 \neq m_2', \dots, m_k \neq m_k'$ také, 
        že $f(h_{i-1}, m_i) = f(h_{i-1}, m_i') = h_i$.

    \item Toto celé vieme spraviť v čase $O(k 2^{n/2})$. A dostaneme $2^k$ 
        kolidujúcich textov (pre každý z $k$ blokov si môžeme vybrať
        2 rôzne texty). Haš každého z nich bude $h_k$.
\end{enumerate}

\begin{figure}[h!]
    \label{fig:joux1}
    \centering
    \includegraphics[scale=1.0]{img/05/joux.1.mps}
    \caption{Útok na multikolíziu}
\end{figure}


Samotný tento útok ešte veľa neznamená. Ale ukazuje sa, že
ho vieme využiť na nájdenie podstatnejších slabín.

Ukážeme si ako ho využiť pri rýchlejšom hľadaní $2^k$-vzoru:
\begin{enumerate}
    \itemsep -1.2mm

    \item Nájdeme $2^k$-kolíziu.

    \item Následne nájdeme posledný blok $m_{k+1}$ tak,
        aby $f(h_k, m_{k+1}) = y$. Toto vieme v čase $O(2^n)$.
\end{enumerate}

\begin{figure}[h!]
    \centering
    \includegraphics[scale=1.0]{img/05/joux.2.mps}
    \caption{Využitie multikolízie pri hľadaní multivzoru}
    \label{fig:joux2}
\end{figure}

Celkový čas hľadania bude $O(2^n)$ namiesto očakávaného $\Theta(k 2^n)$.
Presne rovnako vieme hľadať aj druhý vzor.

\subsubsection{Kaskádové hašovanie}
Niekedy v záujme zvýšenia bezpečnosti zreťazujeme za sebou výstup
dvoch rôznych hašovacích funkcíí, napr.
MD5 a SHA-1. Dostaneme takzvanú kaskádovú hašovaciu funkciu,
formálne $H(m) = H_1(m)||H_2(m)$. 
Ukazuje sa, že ak v jednej z týchto dvoch hašovacích funkcií
vieme efektívne hľadať multikolízie, tak vieme
v kaskádovej hašovacej funkcii hľadať kolízie efektívnejšie
ako len narodeninovým útokom.
Pre jednoduchosť predpokladajme, že obor hodnôt $H_1$
a $H_2$ je $\{0,1\}^n$. Teda dĺžka výstupu $H$ je $2n$, čize
očakávaný čas hľadania kolízie je $\Theta(2^n)$.
Predpokladajme, že $H_1$ je iteratívna. Potom vieme v čase 
$O(\frac{n}{2} 2^{n/2})$ nájsť $2^{n/2}$ kolízií. Tieto dosadíme
na vstup $H_2$ a narodeninový paradox nám zaručí
vysokú úspešnosť nájdenia kolízie aj pre $H_2$. Takto sme dostali
kolíziu pre $H$ v čase $O(\frac{n}{2} 2^{n/2})$.

\subsection{Hľadanie expandovateľnej správy a jej využitie}

Pre útočníka môže byť výhodné mať kolidujúce správy rôznej dĺžky. 
V nasledujúcom texte si popíšeme nájdenie takej multikolízie,
kde všetky správy majú rôzne dĺžky. Nech $m^*$ je ľubovoľný
text dĺžky 1 blok.
Označme si viackrát za sebou použitú kompresnú funkciu $f$ ako
    $F(h_i, a_1||a_2||\dots||a_x) = 
    f(\dots f(f(h_i, a_1), a_2), \dots, a_x)$.
Postup je podobný ako pri hľadaní multikolízie:
\begin{enumerate}
    \itemsep -1.2mm

    \item Položme $h_0 = IV$.

    \item Nájdime $m_1$ a $m_1'$ také, že: 
        $f(h_0, m_1) = f(f(h_0, m^*), m_1') = F(h_0, m^*||m_1') = h_1$. 

    \item Nájdeme ďalšie dvojice $m_2, m_2', \dots, m_k, m_k'$ také, že platí:
        $f(h_{i-1}, m_i) = F(h_{i-1}, (m^*)^{2^{i-1}}||m_i') = h_i$.

    \item Každú dvojicu vieme nájsť v čase $O(2^{n/2})$.
        Celkový čas bude $O(k 2^{n/2})$.
        
        Dostali sme opäť $2^k$ rôznych kolidujúcich textov, ktoré tentokrát 
        majú dlžky $k, k+1, \dots, k+2^k-1$ blokov. 
        Správu požadovanej dĺžky (v blokoch) nájdeme tak, 
        že od jej dĺžky odpočítame $k$ a následne
        sa pozrieme na binárny zápis výsledku postupne odzadu.
        Ak je tam $0$, ideme po hrana, ktorá nemá $m^*$,
        v prípade $1$ ideme po tej druhej.
\end{enumerate}

\begin{figure}[h!]
    \centering
    \includegraphics{img/05/expand.1.mps}
    \caption{Konštrukcia multikolízie rôznej dĺžky}
    \label{fig:expand1}
\end{figure}

\subsubsection{Davis-Meyerova konštrukcia}

Pri niektorých hašovacích funkciách, ktoré využívajú
Davies-Meyerovu konštrukciu vieme expandovateľnú správu hľadať
ešte jednoduchšie. Príkladom môže byť SHA-1, ktorej kompresná funkcia
je definovaná nasledovne:
$f(h, m) = E_m(h)+h$.

Zoberme náhodné $m$. Potom vieme vypočítať tzv. pevný bod, teda vnútorný
stav ktorý sa po \clqq zhašovaní\crqq $m$ nezmení:
\begin{align*}
    f(h,m) &= h \\
    E_m(h) + h&= h \\
    E_m(h) &= 0 \\
    h &= E_m^{-1}(0)
\end{align*}

Útočiť na DM konštrukcie je možné nasledovne -- 
vygenerujme si $2^{n/2}$ správ $m_1, m_2, \dots, m_{2^{n/2}}$
a k ním si vypočítajme pevné body $h_1, h_2, \dots, h_{2^{n/2}}$.
Následne skúšajme postupne rôzne správy $m'$ a hľadajme takú, 
kde $f(h_0, m') = h_i$,$i \in \{1, 2, \dots, 2^{n/2}\}$.
Vďaka narodeninovému paradoxu stačí $2^{n/2}$ pokusov.
Takto sme v čase $O(2^{n/2})$ našli správu, ktorú
vieme ľubovoľne natiahnuť.
\begin{figure}[h!]
    \centering
    \subfigure[Pevný bod]{
        \includegraphics{img/05/expand.3.mps}
        \hspace{1cm}
    }
    \subfigure[Hľadanie kolízií]{
        \includegraphics{img/05/expand.4.mps}
    }

    \caption{Hľadanie kolízií v MD konštrukcii}
\end{figure}

\subsubsection{Hľadanie druhého vzoru}
Následne hľadanie expandovateľnej správy vieme využiť na efektívnejšie
hľadanie druhého vzoru ako hrubou silou.
Majme správu, ktorá je dlhá $l=2^k + k - 1$ blokov.
Zostrojme expandovateľnú správu, ktorá môže nadobúdať dĺžky $k$
až $2^k + k -1$. Jej haš označme ako $h_{expand}$.

Teraz skúšajme nájsť blok $\tilde{m}$ taký, že $f(h_{expand}, \tilde{m})$ 
sa rovná niektorej z hodnôt $h_{k+1}, \dots, h_{k+2^k-1}$.
Ak sa nám podarí nájsť vhodnú hodnotu
(označme ju ako $h_x$), tak môžeme bloky $m_1, m_2, \dots, m_x$ 
nahradiť príslušnou variantou expandovateľnej správy.
Očakávaný počet potrebných pokusov je $\Theta(2^{n-k})$. 

\begin{figure}[h]
    \centering
    \includegraphics{img/05/expand.5.mps}
    \caption{Hľadanie druhého vzoru}
\end{figure}

Čo to v praxi znamená? Zoberme bežne používanú SHA-1, 
ktorej výstup má 160 bitov. Teda,
očákavaný počet operácií pre nájdenie druhého vzoru je úmerný $2^{160}$.
Maximálna dĺžka správy pre SHA-1 je $2^{64} - 1$ bytov,
čo je asi $2^{55}$ blokov.
Zoberme správu dĺžky $54 + 2^{54} - 1$ blokov.
Najprv v čase $2^{80}$ nájdeme expandovateľnú správu (SHA-1 je DM konštrukcia).
Následne potrebujeme ešte $2^{106}$ pokusov na nájdenie 
``spájacieho'' bloku.
Toto je síce stály veľký počet, ale oproti očakávanému počtu $2^{160}$
je to značné zlepšenie.

\subsection{Obrana pred týmto druhom útokov}
Tieto útoky ukazujú, že iteratívna konštrukcia hašovacích funkcií nie je najvhodnejšia.
To, čo ju môže zachrániť je mať aspoň 2-krát dlhší medzistav 
(t.j. hodnoty $h_1, h_2, \dots, h_{k-1}$). Potom sa skomplikuje hľadanie
kolízií v medzistavoch a konštrukcia je proti týmto útokom bezpečná.

\subsection{Nostradamov útok (alebo tiež herding attack)}

Uvažujme nasledujúcu situáciu. Svetovo známy prorok Nostradamus
vyriekne začiatkom roka 2009 proroctvo, týkajúce sa budúcnosti.
Nostradamus je prorok veľkého kalibru a preto vyriekne proroctvá
možné i všemožné, skrátka, natára veľa vecí.
Môže to byť napríklad stav akciového indexu na konci roka 2010.
Akurát ho nezverejní (nechce predsa ovplyvniť burzu, spôsobiť globálnu
ekonomickú krízu, ...) a zverejní len haš tohoto proroctva 
(v podstate je to niečo ako commitment).

Následne na konci roka odhalí svoje proroctvo na svojej stránke.
Haš je v poriadku, proroctvo
o akciách hovorí pravdu, za ním sú ešte nejaké ďalšie proroctvá.
Otázkou je ako veľmi môžeme veriť tomu, že prorok poznal stav
akcií na konci roka. Nostradamus sa nám síce môže snažiť vsugerovať,
že on je naozaj ten pravý prorok, ale je to tak?

Ukazuje sa, že na iteratívnu konštrukciu
hašovacích funkciu existuje tzv. chosen prefix attack.

\subsubsection{Konštrukcia ``proroctva''}

Pripravme si najprv $2^k$ náhodných hodnôt 
$h_{0,1},\ h_{0,2},\ \dots,\ h_{0,2^k}$.
Nad týmito hodnotami ideme vybudovať strom nasledovne:
hľadajme $m_{0,1},\ m_{0,2},\ \dots,\ m_{0,2^k}$ také, že
\begin{align*}
    f(h_{0,1},\ m_{0,1}) &= f(h_{0,2},\ m_{0,2}) = h_{1,1} \\
  &  \dots \\
    f(h_{0,2^k-1},\ m_{0,2^k-1}) &= f(h_{0,2^k},\ m_{0,2^k}) = h_{1,
        2^{k-1}} 
\end{align*}
Následne pokračujme podobným spôsobom aj na ďalších úrovniach
pokiaľ nedostaneme jedinú hodnotu $h_{k,1}$.
Túto hodnotu zverejníme ako haš nášho proroctva.
Navyše, požadujeme, aby tieto správy dávali aspoň nejaký zmysel --
tieto správy totiž budeme potrebovať ``prilepiť'' na koniec celého
proroctva.

Aký čas strávime prípravou tohoto stromu?
Nájdenie jednej kolízie trvá čas $O(2^{n/2})$, na prvej úrovni treba 
$2^{k-1}$ kolízii, na druhej $2^{k-2}$ a na poslednej
potrebujeme jednu kolíziu. Celkový čas je teda
$O\big(2^{n/2} (2^{k-1} + 2^{k-2} + \dots + 1)\big) = O(2^{n/2} 2^k)$.
Lepší spôsob je nehľadať kolízie na jednotlivých úrovniach po dvojiciach,
ale rovno pre celú úroveň.
Vtedy na prvej úrovni strávime čas $O(2^{k/2 + n/2})$.\footnote{
    Aspoň toto tvrdí Stanek. Na prvý pohľad to nie je zrejmé.}
Na druhej úrovni strávime čas $O(2^{k/4 + n/2})$ atď.
Celkový čas bude $O(2^{k/2 + n/2})$.

\begin{figure}[h]
    \centering
    \includegraphics[scale=0.9]{img/05/nostradamus.1.mps}
\end{figure}

Nostradamus na konci roka (po zatvorení burzy) zistí stav akciového
trhu a pripraví si podľa neho správu.
Označme ju $m$. Po jej zahašovaní sa dostaneme do odtlačku
$h_m$. Teraz hľadáme správu $\tilde{m}$, pre ktorú platí
$f(h_m, \tilde{m}) = h_{0,x_0}$, kde $x_0 \in \{1, 2, \dots, 2^k\}$.
Následne na základe pripraveného stromu vieme za správu dolepiť patričné 
$m_{0,x_0},\ m_{1,x_1},\ \dots,\ m_{k,x_k}$ také, že
výsledný haš bude predtým zverejnený $h_{k,1}$.
Teda na konci zverejníme správu 
$m || \tilde{m} || m_{0,x_0} || m_{1,x_1} || \dots || m_{k, 1}$.

Čas hľadania $\tilde{m}$ bude $2^{n-k}$.

\subsubsection{Celkový čas útoku}
Bolo by dobré, aby čas trvania oboch častí útoku bol viacmenej vyvážený. 
Uvažujme najprv pomalšiu variantu predspracovania.
Vtedy chceme, aby $2^{n-k} = 2^{k+n/2}$, z čoho dostaneme
$k=n/4$ a celkový čas bude $2^{3n/4}$.
Pri rýchlejšom predspracovaní máme podmienku $2^{n-k} = 2^{k/2 + n/2}$,
z čoho máme $k = n/3$ a celkový čas $2^{2n/3}$.

\fixme{realne priklady}
